package jacktgq.mazeSolver.generator;

import jacktgq.AlgoVisHelper;

import java.awt.*;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class AlgoVisualizer {
    private AlgoFrame frame;
    private boolean isAnimated = true;
    private MazeData mazeData;
    private enum Algorithm {
        DFS,
        DFSNONRECURSIVE,
        BFS,
        RANDOMQUEUE,
        ENHANCEDRANDOMQUEUE
    }

    private static final int BLOCK_WIDTH = 8;
    private static final int BLOCK_HEIGHT = 8;
    private static final int DELAY = 2;
    private int M = 101;
    private int N = 101;

    public AlgoVisualizer(String filename){
        // 101 x 101的迷宫，假设每一格宽度为BLOCK_WIDTH，高度为BLOCK_HEIGHT个像素
        int sceneWidth = BLOCK_WIDTH * N;
        int sceneHeight = BLOCK_HEIGHT * M;

        mazeData = new MazeData(filename);
        // mazeSolver();
        // System.out.println(mazeData);
        // 初始化视图
        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame("迷宫游戏", sceneWidth, sceneHeight, mazeData);
            frame.addKeyListener(new AlgoKeyListener());
            // frame.addMouseListener(new AlgoMouseListener());
        });
    }

    public AlgoVisualizer(int M, int N){
        // 101 x 101的迷宫，假设每一格宽度为BLOCK_WIDTH，高度为BLOCK_HEIGHT个像素
        int sceneWidth = BLOCK_WIDTH * N;
        int sceneHeight = BLOCK_HEIGHT * M;
        mazeData = new MazeData(M, N);
        // 初始化视图
        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame("迷宫游戏", sceneWidth, sceneHeight, mazeData);
            frame.addKeyListener(new AlgoKeyListener());
            // frame.addMouseListener(new AlgoMouseListener());
        });
    }

    private class AlgoKeyListener extends KeyAdapter {
        boolean operateIsGenerate;
        Algorithm algorithm;
        Thread t1;
        Thread t2;
        @Override
        public void keyReleased(KeyEvent event){
            switch (event.getKeyCode()) {
                case KeyEvent.VK_1:
                    algorithm = Algorithm.DFS;
                    operateIsGenerate = true;
                    break;
                case KeyEvent.VK_2:
                    algorithm = Algorithm.DFSNONRECURSIVE;
                    operateIsGenerate = true;
                    break;
                case KeyEvent.VK_3:
                    algorithm = Algorithm.BFS;
                    operateIsGenerate = true;
                    break;
                case KeyEvent.VK_4:
                    algorithm = Algorithm.RANDOMQUEUE;
                    operateIsGenerate = true;
                    break;
                case KeyEvent.VK_5:
                    algorithm = Algorithm.ENHANCEDRANDOMQUEUE;
                    operateIsGenerate = true;
                    break;
                case KeyEvent.VK_7:
                    algorithm = Algorithm.DFS;
                    operateIsGenerate = false;
                    break;
                case KeyEvent.VK_8:
                    algorithm = Algorithm.DFSNONRECURSIVE;
                    operateIsGenerate = false;
                    break;
                case KeyEvent.VK_9:
                    algorithm = Algorithm.BFS;
                    operateIsGenerate = false;
                    break;
                case KeyEvent.VK_0:
                    mazeData.resetMaze();
                    mazeData.resetMarkedArray();
                    frame.render(mazeData);
                    return;
                default:
                    return;
            }
            if (operateIsGenerate) {
                // 开始生成迷宫前需要确保没有其他线程正在生成迷宫和求解迷宫
                if ((t1 == null || (t1 != null && !t1.isAlive())) && (t2 == null || (t2 != null && !t2.isAlive()))) {
                    // 开始生成随机迷宫
                    t1 = new Thread(() -> {
                        runGenerateMaze(algorithm);
                    });
                    t1.start();
                }
            } else {
                // 开始求解迷宫前需要确保没有其他线程正在生成迷宫和求解迷宫
                if ((t1 == null || (t1 != null && !t1.isAlive())) && (t2 == null || (t2 != null && !t2.isAlive()))) {
                    // 开始生成随机迷宫
                    t2 = new Thread(() -> {
                        runSolveMaze(algorithm);
                    });
                    t2.start();
                }
            }

        }
    }

    /*private class AlgoMouseListener extends MouseAdapter{
        @Override
        public void mouseReleased(MouseEvent event){
        }
    }*/

    // ========================生成迷宫==================================
    // 生成迷宫，将路改成墙，修改可视化数据，并重新渲染
    private void changeWallToRoad(int x, int y) {
        if (mazeData.inArea(x, y)) {
            mazeData.setMazeDataAt(x, y, MazeData.ROAD);
        }
        frame.render(mazeData);
        AlgoVisHelper.pause(DELAY);
    }

    // 生成迷宫动画逻辑
    private void runGenerateMaze(Algorithm algorithm){
        // 复位visited、path、result数组
        mazeData.resetMarkedArray();
        // 复位迷宫初始状态
        mazeData.resetMaze();
        // 绘制数据
        changeWallToRoad(-1, -1);
        switch (algorithm) {
            case DFS:
                generateMazeWithDFS(mazeData.getEntranceX(), mazeData.getEntranceY() + 1);
                break;
            case DFSNONRECURSIVE:
                generateMazeWithDFSNonrecursive(mazeData.getEntranceX(), mazeData.getEntranceY() + 1);
                break;
            case BFS:
                generateMazeWithBFS(mazeData.getEntranceX(), mazeData.getEntranceY() + 1);
                break;
            case RANDOMQUEUE:
                generateMazeWithRandomQueue(mazeData.getEntranceX(), mazeData.getEntranceY() + 1);
            case ENHANCEDRANDOMQUEUE:
                generateMazeWithEnhancedRandomQueue(mazeData.getEntranceX(), mazeData.getEntranceY() + 1);
                break;
        }
        changeWallToRoad(-1, -1);
    }

    /**
     * 深度优先遍历方式生成一个迷宫
     * @param x     ：行数
     * @param y     ：列数
     */
    private void generateMazeWithDFS(int x, int y) {
        mazeData.visited[x][y] = true;
        mazeData.openDenseFog(x, y);
        // 去4个方向跳过一堵墙进行深度优先遍历
        for (int i = 0; i < dirs.length; i++) {
            int nextX = x + dirs[i][0] * 2;
            int nextY = y + dirs[i][1] * 2;
            // 继续寻找下一个位置必须满足下面三个条件
            // 1. 位置必须合法，没有超出边界
            // 2. 下一个位置没有被遍历过
            // 3. 下一个位置是路（由于已经做好了准备工作，隔了一堵墙肯定是路，可以不考虑）
            if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY]) {
                // 打破两个路之间的墙（即，将墙改成路）
                changeWallToRoad(x + dirs[i][0], y + dirs[i][1]);
                generateMazeWithDFS(nextX, nextY);
            }
        }
    }

    /**
     * 深度优先遍历非递归算法生成一个迷宫
     * @param x     ：行数
     * @param y     ：列数
     */
    private void generateMazeWithDFSNonrecursive(int x, int y) {
        Stack<Position> stack = new Stack<>();
        stack.push(new Position(x, y));
        mazeData.visited[x][y] = true;
        mazeData.openDenseFog(x, y);
        while (!stack.isEmpty()) {
            Position positon = stack.pop();
            for (int i = 0; i < dirs.length; i++) {
                int nextX = positon.x + dirs[i][0] * 2;
                int nextY = positon.y + dirs[i][1] * 2;
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY]) {
                    stack.push(new Position(nextX, nextY));
                    mazeData.visited[nextX][nextY] = true;
                    mazeData.openDenseFog(nextX, nextY);
                    changeWallToRoad(positon.x + dirs[i][0], positon.y + dirs[i][1]);
                }
            }
        }
    }

    /**
     * 广度优先遍历算法生成一个迷宫
     * @param x     ：行数
     * @param y     ：列数
     */
    private void generateMazeWithBFS(int x, int y) {
        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(x, y));
        mazeData.visited[x][y] = true;
        mazeData.openDenseFog(x, y);
        while (!queue.isEmpty()) {
            Position positon = queue.remove();
            for (int i = 0; i < dirs.length; i++) {
                int nextX = positon.x + dirs[i][0] * 2;
                int nextY = positon.y + dirs[i][1] * 2;
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY]) {
                    queue.add(new Position(nextX, nextY));
                    mazeData.visited[nextX][nextY] = true;
                    mazeData.openDenseFog(nextX, nextY);
                    changeWallToRoad(positon.x + dirs[i][0], positon.y + dirs[i][1]);
                }
            }
        }
    }

    /**
     * 随机队列遍历算法生成一个迷宫
     * @param x     ：行数
     * @param y     ：列数
     */
    private void generateMazeWithRandomQueue(int x, int y) {
        RandomQueue<Position> queue = new RandomQueue<>();
        queue.enQueue(new Position(x, y));
        mazeData.visited[x][y] = true;
        mazeData.openDenseFog(x, y);
        while (!queue.isEmpty()) {
            Position positon = queue.deQueue();
            for (int i = 0; i < dirs.length; i++) {
                int nextX = positon.x + dirs[i][0] * 2;
                int nextY = positon.y + dirs[i][1] * 2;
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY]) {
                    queue.enQueue(new Position(nextX, nextY));
                    mazeData.visited[nextX][nextY] = true;
                    mazeData.openDenseFog(nextX, nextY);
                    changeWallToRoad(positon.x + dirs[i][0], positon.y + dirs[i][1]);
                }
            }
        }
    }

    /**
     * 增强随机队列遍历算法生成一个迷宫
     * @param x     ：行数
     * @param y     ：列数
     */
    private void generateMazeWithEnhancedRandomQueue(int x, int y) {
        EnhancedRandomQueue<Position> queue = new EnhancedRandomQueue<>();
        queue.enQueue(new Position(x, y));
        mazeData.visited[x][y] = true;
        mazeData.openDenseFog(x, y);
        while (!queue.isEmpty()) {
            Position positon = queue.deQueue();
            for (int i = 0; i < dirs.length; i++) {
                int nextX = positon.x + dirs[i][0] * 2;
                int nextY = positon.y + dirs[i][1] * 2;
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY]) {
                    queue.enQueue(new Position(nextX, nextY));
                    mazeData.visited[nextX][nextY] = true;
                    mazeData.openDenseFog(nextX, nextY);
                    changeWallToRoad(positon.x + dirs[i][0], positon.y + dirs[i][1]);
                }
            }
        }
    }

    // ========================求解迷宫==================================
    // 尝试走这条路，修改可视化数据，并重新渲染
    private void setRoadToPath(int x, int y, boolean isPath) {
        if (mazeData.inArea(x, y)) {
            mazeData.path[x][y] = isPath;
        }
        frame.render(mazeData);
        AlgoVisHelper.pause(DELAY);
    }

    // 求解迷宫动画逻辑
    private void runSolveMaze(Algorithm algorithm){
        // 复位visited、path、result数组
        mazeData.resetMarkedArray();
        // 绘制数据
        setRoadToPath(-1, -1, false);
        boolean hasSolved = false;
        switch (algorithm) {
            case DFS:
                hasSolved = goWithDFS(mazeData.getEntranceX(), mazeData.getEntranceY());
                break;
            case DFSNONRECURSIVE:
                hasSolved = goWithDFSNonrecursive();
                break;
            case BFS:
                hasSolved = goWithBFS();
                break;
        }
        if (hasSolved) {
            System.out.println("迷宫有解");
        } else {
            System.out.println("迷宫无解");
        }
        setRoadToPath(-1, -1, false);
    }

    // 四个方向的偏移量数组
    private static final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    /**
     * 深度优先遍历方式求迷宫的解
     * @param x     ：起始所在行数
     * @param y     ：起始所在列数
     * @return
     */
    private boolean goWithDFS(int x, int y) {
        mazeData.visited[x][y] = true;
        setRoadToPath(x, y, true);

        if (x == mazeData.getExitX() && y == mazeData.getExitY()) {
            return true;
        }

        // 去4个方向深度优先遍历
        for (int i = 0; i < dirs.length; i++) {
            int nextX = x + dirs[i][0];
            int nextY = y + dirs[i][1];
            // 继续寻找下一个位置必须满足下面三个条件
            // 1. 位置必须合法，没有超出边界
            // 2. 下一个位置没有被遍历过
            // 3. 下一个位置是路
            if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY] && mazeData.getMazeDataAt(nextX, nextY) == MazeData.ROAD) {
                // 找到终点，记录一下
                if(goWithDFS(nextX, nextY)) {
                    return true;
                }
            }
        }

        setRoadToPath(x, y, false);
        return false;
    }

    /**
     * 深度优先遍历方式求迷宫的解
     * @return
     */
    private boolean goWithDFSNonrecursive() {
        Stack<Position> stack = new Stack<>();
        int x = mazeData.getEntranceX();
        int y = mazeData.getEntranceY();
        stack.push(new Position(x, y, null));
        mazeData.visited[x][y] = true;
        setRoadToPath(x, y, true);
        while (!stack.isEmpty()) {
            Position pos = stack.pop();
            x = pos.x;
            y = pos.y;
            setRoadToPath(x, y, true);

            if (x == mazeData.getExitX() && y == mazeData.getExitY()) {
                findPath(pos);
                return true;
            }

            for (int i = 0; i < dirs.length; i++) {
                int nextX = x + dirs[i][0];
                int nextY = y + dirs[i][1];
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY] && mazeData.getMazeDataAt(nextX, nextY) == MazeData.ROAD) {
                    stack.add(new Position(nextX, nextY, pos));
                    mazeData.visited[x][y] = true;
                }
            }
        }

        return false;
    }

    /**
     * 从终点开始向前找出路径
     */
    private void findPath(Position pos) {
        while (pos != null) {
            mazeData.result[pos.x][pos.y] = true;
            // System.out.println(cur);
            pos = pos.prev;
        }
    }

    /**
     * 使用广度优先遍历方式求迷宫的解
     * @return
     */
    private boolean goWithBFS() {
        Queue<Position> queue = new LinkedList<>();
        // 将起始位置入队
        int x = mazeData.getEntranceX();
        int y = mazeData.getEntranceY();
        queue.add(new Position(x, y, null));
        mazeData.visited[x][y] = true;
        setRoadToPath(x, y, true);
        while (!queue.isEmpty()) {
            Position pos = queue.remove();
            x = pos.x;
            y = pos.y;
            setRoadToPath(x, y, true);

            if (x == mazeData.getExitX() && y == mazeData.getExitY()) {
                findPath(pos);
                return true;
            }

            for (int i = 0; i < dirs.length; i++) {
                int nextX = x + dirs[i][0];
                int nextY = y + dirs[i][1];
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY] && mazeData.getMazeDataAt(nextX, nextY) == MazeData.ROAD) {
                    queue.add(new Position(nextX, nextY, pos));
                    mazeData.visited[nextX][nextY] = true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        // String filename = "data/maze_101_101.txt";
        AlgoVisualizer visualizer = new AlgoVisualizer(61, 91);
    }
}
